{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Stone Game V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming #game-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划 #博弈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: stoneGameV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #石子游戏 V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>几块石子 <strong>排成一行</strong> ，每块石子都有一个关联值，关联值为整数，由数组 <code>stoneValue</code> 给出。</p>\n",
    "\n",
    "<p>游戏中的每一轮：Alice 会将这行石子分成两个 <strong>非空行</strong>（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。</p>\n",
    "\n",
    "<p>只 <strong>剩下一块石子</strong> 时，游戏结束。Alice 的分数最初为 <strong><code>0</code></strong> 。</p>\n",
    "\n",
    "<p>返回 <strong>Alice 能够获得的最大分数</strong><em> 。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>stoneValue = [6,2,3,4,5,5]\n",
    "<strong>输出：</strong>18\n",
    "<strong>解释：</strong>在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。\n",
    "在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。\n",
    "最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。游戏结束，因为这行只剩下一块石头了。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>stoneValue = [7,7,7,7,7,7,7]\n",
    "<strong>输出：</strong>28\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>stoneValue = [4]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= stoneValue.length &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;=&nbsp;stoneValue[i] &lt;= 10^6</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [stone-game-v](https://leetcode.cn/problems/stone-game-v/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [stone-game-v](https://leetcode.cn/problems/stone-game-v/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[6,2,3,4,5,5]', '[7,7,7,7,7,7,7]', '[4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        maxl = [[0] * n for _ in range(n)]\n",
    "        maxr = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for left in range(n - 1, -1, -1):\n",
    "            maxl[left][left] = maxr[left][left] = stoneValue[left]\n",
    "            total = stoneValue[left]\n",
    "            suml = 0\n",
    "            i = left - 1\n",
    "            for right in range(left + 1, n):\n",
    "                total += stoneValue[right]\n",
    "                while i + 1 < right and (suml + stoneValue[i + 1]) * 2 <= total:\n",
    "                    suml += stoneValue[i + 1]\n",
    "                    i += 1\n",
    "                if left <= i:\n",
    "                    f[left][right] = max(f[left][right], maxl[left][i])\n",
    "                if i + 1 < right:\n",
    "                    f[left][right] = max(f[left][right], maxr[i + 2][right])\n",
    "                if suml * 2 == total:\n",
    "                    f[left][right] = max(f[left][right], maxr[i + 1][right])\n",
    "                maxl[left][right] = max(maxl[left][right - 1], total + f[left][right])\n",
    "                maxr[left][right] = max(maxr[left + 1][right], total + f[left][right])\n",
    "        \n",
    "        return f[0][n - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        maxl = [[0] * n for _ in range(n)]\n",
    "        maxr = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for left in range(n - 1, -1, -1):\n",
    "            maxl[left][left] = maxr[left][left] = stoneValue[left]\n",
    "            total = stoneValue[left]\n",
    "            suml = 0\n",
    "            i = left - 1\n",
    "            for right in range(left + 1, n):\n",
    "                total += stoneValue[right]\n",
    "                while i + 1 < right and (suml + stoneValue[i + 1]) * 2 <= total:\n",
    "                    suml += stoneValue[i + 1]\n",
    "                    i += 1\n",
    "                if left <= i:\n",
    "                    f[left][right] = max(f[left][right], maxl[left][i])\n",
    "                if i + 1 < right:\n",
    "                    f[left][right] = max(f[left][right], maxr[i + 2][right])\n",
    "                if suml * 2 == total:\n",
    "                    f[left][right] = max(f[left][right], maxr[i + 1][right])\n",
    "                maxl[left][right] = max(maxl[left][right - 1], total + f[left][right])\n",
    "                maxr[left][right] = max(maxr[left + 1][right], total + f[left][right])\n",
    "        \n",
    "        return f[0][n - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        maxl = [[0] * n for _ in range(n)]\n",
    "        maxr = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for left in range(n - 1, -1, -1):\n",
    "            maxl[left][left] = maxr[left][left] = stoneValue[left]\n",
    "            total = stoneValue[left]\n",
    "            suml = 0\n",
    "            i = left - 1\n",
    "            for right in range(left + 1, n):\n",
    "                total += stoneValue[right]\n",
    "                while i + 1 < right and (suml + stoneValue[i + 1]) * 2 <= total:\n",
    "                    suml += stoneValue[i + 1]\n",
    "                    i += 1\n",
    "                if left <= i:\n",
    "                    f[left][right] = max(f[left][right], maxl[left][i])\n",
    "                if i + 1 < right:\n",
    "                    f[left][right] = max(f[left][right], maxr[i + 2][right])\n",
    "                if suml * 2 == total:\n",
    "                    f[left][right] = max(f[left][right], maxr[i + 1][right])\n",
    "                maxl[left][right] = max(maxl[left][right - 1], total + f[left][right])\n",
    "                maxr[left][right] = max(maxr[left + 1][right], total + f[left][right])\n",
    "        \n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        s, maxl, maxr = [[0] * n for _ in range(n)], [[0] * n for _ in range(n)], [[0] * n for _ in range(n)]\n",
    "        for l in range(n - 1, -1, -1):\n",
    "            maxl[l][l] = maxr[l][l] = stoneValue[l]\n",
    "            total = stoneValue[l]\n",
    "            suml = 0\n",
    "            i = l - 1\n",
    "            for r in range(l + 1, n):\n",
    "                total += stoneValue[r]\n",
    "                while i + 1 < r and (suml + stoneValue[i + 1]) * 2 <= total:\n",
    "                    suml += stoneValue[i + 1]\n",
    "                    i += 1\n",
    "                if l <= i:\n",
    "                    s[l][r] = max(s[l][r], maxl[l][i])\n",
    "                if i + 1 < r:\n",
    "                    s[l][r] = max(s[l][r], maxr[i + 2][r])\n",
    "                if suml * 2 == total:\n",
    "                    s[l][r] = max(s[l][r], maxr[i + 1][r])\n",
    "                maxl[l][r] = max(maxl[l][r - 1], total + s[l][r])\n",
    "                maxr[l][r] = max(maxr[l + 1][r], total + s[l][r])\n",
    "        return s[0][n - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        maxl = [[0] * n for _ in range(n)]\n",
    "        maxr = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for left in range(n - 1, -1, -1):\n",
    "            maxl[left][left] = maxr[left][left] = stoneValue[left]\n",
    "            total = stoneValue[left]\n",
    "            suml = 0\n",
    "            i = left - 1\n",
    "            for right in range(left + 1, n):\n",
    "                total += stoneValue[right]\n",
    "                while i + 1 < right and (suml + stoneValue[i + 1]) * 2 <= total:\n",
    "                    suml += stoneValue[i + 1]\n",
    "                    i += 1\n",
    "                if left <= i:\n",
    "                    f[left][right] = max(f[left][right], maxl[left][i])\n",
    "                if i + 1 < right:\n",
    "                    f[left][right] = max(f[left][right], maxr[i + 2][right])\n",
    "                if suml * 2 == total:\n",
    "                    f[left][right] = max(f[left][right], maxr[i + 1][right])\n",
    "                maxl[left][right] = max(maxl[left][right - 1], total + f[left][right])\n",
    "                maxr[left][right] = max(maxr[left + 1][right], total + f[left][right])\n",
    "        \n",
    "        return f[0][n - 1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        maxl = [[0] * n for _ in range(n)]\n",
    "        maxr = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for left in range(n - 1, -1, -1):\n",
    "            maxl[left][left] = maxr[left][left] = stoneValue[left]\n",
    "            total = stoneValue[left]\n",
    "            suml = 0\n",
    "            i = left - 1\n",
    "            for right in range(left + 1, n):\n",
    "                total += stoneValue[right]\n",
    "                while i + 1 < right and (suml + stoneValue[i + 1]) * 2 <= total:\n",
    "                    suml += stoneValue[i + 1]\n",
    "                    i += 1\n",
    "                if left <= i:\n",
    "                    f[left][right] = max(f[left][right], maxl[left][i])\n",
    "                if i + 1 < right:\n",
    "                    f[left][right] = max(f[left][right], maxr[i + 2][right])\n",
    "                if suml * 2 == total:\n",
    "                    f[left][right] = max(f[left][right], maxr[i + 1][right])\n",
    "                maxl[left][right] = max(maxl[left][right - 1], total + f[left][right])\n",
    "                maxr[left][right] = max(maxr[left + 1][right], total + f[left][right])\n",
    "        \n",
    "        return f[0][n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        maxl = [[0] * n for _ in range(n)]\n",
    "        maxr = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for left in range(n - 1, -1, -1):\n",
    "            maxl[left][left] = maxr[left][left] = stoneValue[left]\n",
    "            total = stoneValue[left]\n",
    "            suml = 0\n",
    "            i = left - 1\n",
    "            for right in range(left + 1, n):\n",
    "                total += stoneValue[right]\n",
    "                while i + 1 < right and (suml + stoneValue[i + 1]) * 2 <= total:\n",
    "                    suml += stoneValue[i + 1]\n",
    "                    i += 1\n",
    "                if left <= i:\n",
    "                    f[left][right] = max(f[left][right], maxl[left][i])\n",
    "                if i + 1 < right:\n",
    "                    f[left][right] = max(f[left][right], maxr[i + 2][right])\n",
    "                if suml * 2 == total:\n",
    "                    f[left][right] = max(f[left][right], maxr[i + 1][right])\n",
    "                maxl[left][right] = max(maxl[left][right - 1], total + f[left][right])\n",
    "                maxr[left][right] = max(maxr[left + 1][right], total + f[left][right])\n",
    "        \n",
    "        return f[0][n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        maxl = [[0] * n for _ in range(n)]\n",
    "        maxr = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for left in range(n - 1, -1, -1):\n",
    "            maxl[left][left] = maxr[left][left] = stoneValue[left]\n",
    "            total = stoneValue[left]\n",
    "            suml = 0\n",
    "            i = left - 1\n",
    "            for right in range(left + 1, n):\n",
    "                total += stoneValue[right]\n",
    "                \n",
    "                while i + 1 < right and (suml + stoneValue[i + 1]) * 2 <= total:\n",
    "                    suml += stoneValue[i + 1]\n",
    "                    i += 1\n",
    "                if left <= i:\n",
    "                    f[left][right] = max(f[left][right], maxl[left][i])\n",
    "                if i + 1 < right:\n",
    "                    f[left][right] = max(f[left][right], maxr[i + 2][right])\n",
    "                if suml * 2 == total:\n",
    "                    f[left][right] = max(f[left][right], maxr[i + 1][right])\n",
    "                maxl[left][right] = max(maxl[left][right - 1], total + f[left][right])\n",
    "                maxr[left][right] = max(maxr[left + 1][right], total + f[left][right])\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        memo = [[0]*n for _ in range(n)]\n",
    "        maxLeft = [[0]*n for _ in range(n)]\n",
    "        maxRight = [[0]*n for _ in range(n)]\n",
    "        accum = [0]\n",
    "        for v in stoneValue:\n",
    "            accum.append(accum[-1]+v)\n",
    "\n",
    "        for left in range(n-1, -1, -1):\n",
    "            maxLeft[left][left] = maxRight[left][left] = stoneValue[left]\n",
    "            sumVal = stoneValue[left]\n",
    "            leftSumVal = 0\n",
    "            mid = left-1\n",
    "            for right in range(left+1, n):\n",
    "                sumVal += stoneValue[right]\n",
    "                while mid+1 < right and (leftSumVal+stoneValue[mid+1])*2 <= sumVal:\n",
    "                    leftSumVal += stoneValue[mid+1]\n",
    "                    mid += 1\n",
    "                if left <= mid:\n",
    "                    memo[left][right] = max(\n",
    "                        memo[left][right], maxLeft[left][mid])\n",
    "                if mid+1 < right:\n",
    "                    memo[left][right] = max(\n",
    "                        memo[left][right], maxRight[mid+2][right])\n",
    "                if leftSumVal*2 == sumVal:\n",
    "                    memo[left][right] = max(\n",
    "                        memo[left][right], maxRight[mid+1][right])\n",
    "                maxLeft[left][right] = max(\n",
    "                    maxLeft[left][right-1], sumVal+memo[left][right])\n",
    "                maxRight[left][right] = max(\n",
    "                    maxRight[left+1][right], sumVal+memo[left][right])\n",
    "        return memo[0][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        maxl, maxr = [[0] * n for _ in range(n)],[[0] * n for _ in range(n)]\n",
    "\n",
    "        for l in range(n-1,-1,-1):\n",
    "            maxl[l][l] = maxr[l][l] = stoneValue[l]\n",
    "            total = stoneValue[l]\n",
    "            suml = 0\n",
    "            i = l - 1\n",
    "\n",
    "            for r in range(l+1,n):\n",
    "                total += stoneValue[r]\n",
    "\n",
    "                while i + 1 < r and (suml + stoneValue[i+1]) * 2 <= total:\n",
    "                    suml += stoneValue[i+1]\n",
    "                    i += 1\n",
    "                \n",
    "                if l <= i:\n",
    "                    f[l][r] = max(f[l][r],maxl[l][i])\n",
    "                \n",
    "                if i + 1 < r:\n",
    "                    f[l][r] = max(f[l][r],maxr[i+2][r])\n",
    "                \n",
    "                if suml*2 == total:\n",
    "                    f[l][r] = max(f[l][r],maxr[i+1][r])\n",
    "                \n",
    "                maxl[l][r] = max(maxl[l][r-1], total + f[l][r])\n",
    "                maxr[l][r] = max(maxr[l+1][r], total + f[l][r])\n",
    "        \n",
    "        return f[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        maxl = [[0] * n for _ in range(n)]\n",
    "        maxr = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for left in range(n - 1, -1, -1):\n",
    "            maxl[left][left] = maxr[left][left] = stoneValue[left]\n",
    "            total = stoneValue[left]\n",
    "            suml = 0\n",
    "            i = left - 1\n",
    "            for right in range(left + 1, n):\n",
    "                total += stoneValue[right]\n",
    "                \n",
    "                while i + 1 < right and (suml + stoneValue[i + 1]) * 2 <= total:\n",
    "                    suml += stoneValue[i + 1]\n",
    "                    i += 1\n",
    "                if left <= i:\n",
    "                    f[left][right] = max(f[left][right], maxl[left][i])\n",
    "                if i + 1 < right:\n",
    "                    f[left][right] = max(f[left][right], maxr[i + 2][right])\n",
    "                if suml * 2 == total:\n",
    "                    f[left][right] = max(f[left][right], maxr[i + 1][right])\n",
    "                maxl[left][right] = max(maxl[left][right - 1], total + f[left][right])\n",
    "                maxr[left][right] = max(maxr[left + 1][right], total + f[left][right])\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        points = [[0] * n for _ in range(n)]\n",
    "        mxl = [[0] * n for _ in range(n)]\n",
    "        mxr = [[0] * n for _ in range(n)]\n",
    "        prefix = [0]\n",
    "\n",
    "        for i in range(n):\n",
    "            points[i][i] = i\n",
    "            mxl[i][i] = stoneValue[i]\n",
    "            mxr[i][i] = stoneValue[i]\n",
    "            prefix.append(prefix[-1] + stoneValue[i])\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                k = points[i][j - 1]\n",
    "                total = prefix[j + 1] - prefix[i]\n",
    "                while total - prefix[k + 1] + prefix[i] > prefix[k + 1] - prefix[i]:\n",
    "                    k += 1\n",
    "                points[i][j] = k\n",
    "                \n",
    "        for j in range(1, n):\n",
    "            for i in range(j - 1, -1, -1):\n",
    "                k = points[i][j]\n",
    "                left, right = prefix[k + 1] - prefix[i], prefix[j + 1] - prefix[k + 1]\n",
    "                if left == right:\n",
    "                    dp[i][j] = max(dp[i][j], mxl[i][k], mxr[k + 1][j])\n",
    "                else:\n",
    "                    if k > i:\n",
    "                        dp[i][j] = max(dp[i][j], mxl[i][k - 1])\n",
    "                    if k < j:\n",
    "                        dp[i][j] = max(dp[i][j], mxr[k + 1][j])\n",
    "                \n",
    "                mxl[i][j] = max(mxl[i][j - 1], dp[i][j] + prefix[j + 1] - prefix[i])\n",
    "                mxr[i][j] = max(mxr[i + 1][j], dp[i][j] + prefix[j + 1] - prefix[i])\n",
    "        \n",
    "        return dp[0][-1]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    区间DP + 博弈论DP\n",
    "    比较难理解，该写法是基于 https://leetcode.cn/problems/stone-game-v/submissions/467309295/ 的常规思路的优化\n",
    "    常规思路中递归两个入参组合的可能性为n * n，而递归内部又需要在两个入参内循环遍历所可能，又是一个n，因此最终的时间复杂度为\n",
    "    n^3，会超时，该优化方法就是将内部的区间遍历变成O(1)时间\n",
    "    基于如下的想法\n",
    "    在[i, j]的区间内一定存在一个k点，使得sum[i, k] 第一次大于等于 sum[k + 1, j]的，也可以用sum[i, k]最后一次小于等于sum[k + 1, j]，\n",
    "    具体使用哪个看个人习惯，这里用第一种定义，不同的k取值在代码的处理上有一定的差异（第二种处理方式可以参考官解）\n",
    "    由于数组都是正整数，所以当计算出[i, j]的特殊点k，当j变成j + 1时，我们只需要依赖k往后推导一次就能得到在[i, j + 1]区间上满足上述要求\n",
    "    的分割点k'，通过这种方式就可以将所有区间的分割点先算出来\n",
    "    \n",
    "    '''\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        points = [[0] * n for _ in range(n)]\n",
    "        mxl = [[0] * n for _ in range(n)]\n",
    "        mxr = [[0] * n for _ in range(n)]\n",
    "        prefix = [0]\n",
    "\n",
    "        for i in range(n):\n",
    "            points[i][i] = i\n",
    "            mxl[i][i] = stoneValue[i]\n",
    "            mxr[i][i] = stoneValue[i]\n",
    "            prefix.append(prefix[-1] + stoneValue[i])\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                k = points[i][j - 1]\n",
    "                total = prefix[j + 1] - prefix[i]\n",
    "                '''\n",
    "                算第一个左边大于右边的点\n",
    "                '''\n",
    "                while total - prefix[k + 1] + prefix[i] > prefix[k + 1] - prefix[i]:\n",
    "                    k += 1\n",
    "                points[i][j] = k\n",
    "\n",
    "        '''\n",
    "        下面注释中的代码为什么不能替换注释下的代码，还没能理解（想了好几天没有想通），暂留疑问\n",
    "        '''\n",
    "        for j in range(1, n):\n",
    "            for i in range(j - 1, -1, -1):\n",
    "                k = points[i][j]\n",
    "                left, right = prefix[k + 1] - prefix[i], prefix[j + 1] - prefix[k + 1]\n",
    "                if left == right:\n",
    "                    # dp[i][j] = max(dp[i][j], dp[i][k], dp[k + 1][j])\n",
    "                    dp[i][j] = max(dp[i][j], mxl[i][k], mxr[k + 1][j])\n",
    "                else:\n",
    "                    '''\n",
    "                    因为上面的k其实是中间偏右的概念，因此可能k == i或者k == j，此时再用 k - 1或者\n",
    "                    k + 1就会有问题，比如[1, 3]，第一个左边大于右边的k = 1，此时k == j了，再判断\n",
    "                    k + 1就会溢出，所以这里要有两个判断\n",
    "                    '''\n",
    "                    if k > i:\n",
    "                        # dp[i][j] = max(dp[i][j], dp[i][k - 1] + prefix[k] - prefix[i])\n",
    "                        '''\n",
    "                        dp[i][k - 1]\n",
    "                        dp[i][p]\n",
    "                        '''\n",
    "                        dp[i][j] = max(dp[i][j], mxl[i][k - 1])\n",
    "                    if k < j:\n",
    "                        # dp[i][j] = max(dp[i][j], dp[k + 1][j] + prefix[j + 1] - prefix[k + 1])\n",
    "                        dp[i][j] = max(dp[i][j], mxr[k + 1][j])\n",
    "                \n",
    "                mxl[i][j] = max(mxl[i][j - 1], dp[i][j] + prefix[j + 1] - prefix[i])\n",
    "                mxr[i][j] = max(mxr[i + 1][j], dp[i][j] + prefix[j + 1] - prefix[i])\n",
    "        return dp[0][-1]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        presum = [0]\n",
    "        middle = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        leftMax = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        rightMax = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i, s in enumerate(stoneValue):\n",
    "            presum.append(presum[-1] + s)\n",
    "            middle[i][i] = i\n",
    "            leftMax[i][i] = stoneValue[i]\n",
    "            rightMax[i][i] = stoneValue[i]\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                mid = middle[i][j - 1]\n",
    "                while mid < j and presum[j + 1] - presum[mid + 1] > presum[mid + 1] - presum[i]:\n",
    "                    mid += 1 \n",
    "                middle[i][j] = mid\n",
    "        for l in range(2, n + 1):\n",
    "            for i in range(n - l + 1):\n",
    "                j = i + l - 1 \n",
    "                mid = middle[i][j]\n",
    "                if i < mid:\n",
    "                    dp[i][j] = max(leftMax[i][mid - 1] , dp[i][j])\n",
    "                if j > mid:\n",
    "                    dp[i][j] = max(rightMax[mid + 1][j], dp[i][j])\n",
    "                if presum[j + 1] - presum[mid + 1] == presum[mid + 1] - presum[i]:\n",
    "                    dp[i][j] = max(dp[i][j], leftMax[i][mid])\n",
    "                leftMax[i][j] = max(leftMax[i][j - 1], dp[i][j] + presum[j + 1] - presum[i])   \n",
    "                rightMax[i][j] = max(rightMax[i + 1][j], dp[i][j] + presum[j + 1] - presum[i])\n",
    "        return dp[0][-1]             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        points = [[0] * n for _ in range(n)]\n",
    "        mxl = [[0] * n for _ in range(n)]\n",
    "        mxr = [[0] * n for _ in range(n)]\n",
    "        prefix = [0]\n",
    "\n",
    "        for i in range(n):\n",
    "            points[i][i] = i\n",
    "            mxl[i][i] = stoneValue[i]\n",
    "            mxr[i][i] = stoneValue[i]\n",
    "            prefix.append(prefix[-1] + stoneValue[i])\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                k = points[i][j - 1]\n",
    "                total = prefix[j + 1] - prefix[i]\n",
    "                while total - prefix[k + 1] + prefix[i] > prefix[k + 1] - prefix[i]:\n",
    "                    k += 1\n",
    "                points[i][j] = k\n",
    "        print(points) \n",
    "        for j in range(1, n):\n",
    "            for i in range(j - 1, -1, -1):\n",
    "                k = points[i][j]\n",
    "                left, right = prefix[k + 1] - prefix[i], prefix[j + 1] - prefix[k + 1]\n",
    "                if left == right:\n",
    "                    dp[i][j] = max(dp[i][j], mxl[i][k], mxr[k + 1][j])\n",
    "                else:\n",
    "                    if k > i:\n",
    "                        dp[i][j] = max(dp[i][j], mxl[i][k - 1])\n",
    "                    if k < j:\n",
    "                        dp[i][j] = max(dp[i][j], mxr[k + 1][j])\n",
    "                \n",
    "                mxl[i][j] = max(mxl[i][j - 1], dp[i][j] + prefix[j + 1] - prefix[i])\n",
    "                mxr[i][j] = max(mxr[i + 1][j], dp[i][j] + prefix[j + 1] - prefix[i])\n",
    "        \n",
    "        return dp[0][-1]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        add_sum = list(accumulate(stoneValue, initial=0))\n",
    "        g = [[0]*n for _ in range(n)]\n",
    "        s = [[0]*n for _ in range(n)]\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        maxl = [[0]*n for _ in range(n)]\n",
    "        maxr = [[0]*n for _ in range(n)]\n",
    "        # f(l,r)+sum(l,r)\n",
    "\n",
    "        for i in range(n):\n",
    "            s[i][i] = stoneValue[i]\n",
    "            g[i][i] = i\n",
    "            for j in range(i+1, n):\n",
    "                s[i][j] = s[i][j-1] + stoneValue[j]\n",
    "                now = g[i][j-1]\n",
    "                while s[i][j] > 2*s[i][now]:\n",
    "                    now += 1\n",
    "                g[i][j] = now\n",
    "        \n",
    "        for i in range(n):\n",
    "            dp[i][i] = 0\n",
    "            maxl[i][i] = s[i][i] + dp[i][i]\n",
    "            maxr[i][i] = s[i][i] + dp[i][i]\n",
    "        for L in range(2,n+1):\n",
    "            for i in range(n-L+1):\n",
    "                l,r = i,i+L-1\n",
    "                mid = g[l][r]\n",
    "                if mid < r and s[l][mid]==s[mid+1][r]:\n",
    "                    dp[l][r] = max(dp[l][r], maxl[l][mid])\n",
    "                    dp[l][r] = max(dp[l][r], maxr[mid+1][r])\n",
    "                else:\n",
    "                    if mid>l:\n",
    "                        dp[l][r] = max(dp[l][r], maxl[l][mid-1])\n",
    "                    if mid<r:\n",
    "                        dp[l][r] = max(dp[l][r], maxr[mid+1][r])\n",
    "                \n",
    "                v = dp[l][r] + s[l][r]\n",
    "                maxl[l][r] = max(v, maxl[l][r-1])\n",
    "                maxr[l][r] = max(v, maxr[l+1][r])\n",
    "\n",
    "        return dp[0][n-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        add_sum = list(accumulate(stoneValue, initial=0))\n",
    "        g = [[0]*n for _ in range(n)]\n",
    "        s = [[0]*n for _ in range(n)]\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        maxl = [[0]*n for _ in range(n)]\n",
    "        maxr = [[0]*n for _ in range(n)]\n",
    "        # f(l,r)+sum(l,r)\n",
    "\n",
    "        def cal(left, right)->int:\n",
    "            target = add_sum[right+1]-add_sum[left]\n",
    "            lo = left\n",
    "            ans = -1\n",
    "            while left<=right:\n",
    "                mid = (left+right)//2\n",
    "                if 2*(add_sum[mid+1]-add_sum[lo])>=target:\n",
    "                    ans = mid\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return ans\n",
    "\n",
    "        for i in range(n):\n",
    "            s[i][i] = stoneValue[i]\n",
    "            g[i][i] = i\n",
    "        for L in range(2,n+1):\n",
    "            for i in range(n-L+1):\n",
    "                l,r = i,i+L-1\n",
    "                s[l][r] = add_sum[r+1]-add_sum[l]\n",
    "                g[l][r] = cal(l,r)\n",
    "        \n",
    "        for i in range(n):\n",
    "            dp[i][i] = 0\n",
    "            maxl[i][i] = s[i][i] + dp[i][i]\n",
    "            maxr[i][i] = s[i][i] + dp[i][i]\n",
    "        for L in range(2,n+1):\n",
    "            for i in range(n-L+1):\n",
    "                l,r = i,i+L-1\n",
    "                mid = g[l][r]\n",
    "                if mid < r and s[l][mid]==s[mid+1][r]:\n",
    "                    dp[l][r] = max(dp[l][r], maxl[l][mid])\n",
    "                    dp[l][r] = max(dp[l][r], maxr[mid+1][r])\n",
    "                else:\n",
    "                    if mid>l:\n",
    "                        dp[l][r] = max(dp[l][r], maxl[l][mid-1])\n",
    "                    if mid<r:\n",
    "                        dp[l][r] = max(dp[l][r], maxr[mid+1][r])\n",
    "                \n",
    "                v = dp[l][r] + s[l][r]\n",
    "                maxl[l][r] = max(v, maxl[l][r-1])\n",
    "                maxr[l][r] = max(v, maxr[l+1][r])\n",
    "\n",
    "        return dp[0][n-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "\n",
    "        stoneValue = [0] + stoneValue\n",
    "        pre = list(accumulate(stoneValue))\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            M = 0 \n",
    "            for k in range(i, j+1):\n",
    "                s = 0 \n",
    "                left = pre[k] - pre[i-1]\n",
    "                right = pre[j] - pre[k]\n",
    "                if left > right:\n",
    "                    if 2 * right <= M:\n",
    "                        break\n",
    "                    s += right \n",
    "                    s += f(k+1, j)\n",
    "                elif left < right:\n",
    "                    if 2 * left <= M:\n",
    "                        continue\n",
    "                    s += left \n",
    "                    s += f(i, k)\n",
    "                else:\n",
    "                    s += left \n",
    "                    s += max(f(i, k), f(k+1, j))\n",
    "                M = max(M, s)\n",
    "            return M\n",
    "        return f(1, len(stoneValue)-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        pres = list(accumulate(stoneValue, initial=0))\n",
    "        n = len(stoneValue)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            # print(l, r)\n",
    "            if l >= r:\n",
    "                return 0\n",
    "            res = -inf\n",
    "            for i in range(l, r):\n",
    "                left, right = pres[i + 1] - pres[l], pres[r + 1] - pres[i + 1]\n",
    "                if left == right:\n",
    "                    res = max(res, dfs(l, i) + left, dfs(i + 1, r) + right)\n",
    "                elif left < right:\n",
    "                    if res >= 2 * left:\n",
    "                        continue\n",
    "                    res = max(res, dfs(l, i) + left)\n",
    "                else:\n",
    "                    if 2 * right <= res:\n",
    "                        break\n",
    "                    res = max(res, dfs(i + 1, r) + right)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        # 前缀和\n",
    "        S = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            S[i] = S[i-1] + stoneValue[i-1]\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            total = S[j+1] - S[i]\n",
    "            sum = 0\n",
    "            count = 0\n",
    "            for k in range(i,j+1):\n",
    "                sum += stoneValue[k]\n",
    "                if sum == total-sum:\n",
    "                    count = max(sum + max(dfs(i,k),dfs(k+1,j)),count)\n",
    "                elif sum < total-sum:\n",
    "                    # 剪个枝\n",
    "                    if count >= 2*sum:\n",
    "                        continue\n",
    "                    count = max(sum+dfs(i,k),count)\n",
    "                else:\n",
    "                    # 剪个枝\n",
    "                    if 2*(total - sum) <= count:\n",
    "                        break\n",
    "                    count = max(count,total-sum+dfs(k+1,j))\n",
    "            return count    \n",
    "        return dfs(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        pre = list(accumulate(stoneValue))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(l,r):\n",
    "            if l >= r:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for i in range(l,r):\n",
    "                #处理 l-1 < 0\n",
    "                sum1 = pre[i] - (pre[l-1] if l!=0 else 0)\n",
    "                sum2 = pre[r] - pre[i]\n",
    "                if sum1 > sum2:\n",
    "                    if 2*sum2 <= ans:\n",
    "                        break\n",
    "                    ans = max(ans,sum2 + dfs(i+1,r))\n",
    "                elif sum1 < sum2:\n",
    "                    if ans >= 2*sum1:\n",
    "                        continue\n",
    "                    ans = max(ans,sum1 + dfs(l,i))\n",
    "                else:\n",
    "                    ans = max(ans,max(dfs(i+1,r),dfs(l,i))+sum1)\n",
    "            return ans\n",
    "        return dfs(0,len(stoneValue)-1)\n",
    "\n",
    "# class Solution:\n",
    "#     def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "#         @lru_cache(None)\n",
    "#         def dfs(left: int, right: int) -> int:\n",
    "#             if left == right:\n",
    "#                 return 0\n",
    "            \n",
    "#             total = sum(stoneValue[left:right+1])\n",
    "#             suml = ans = 0\n",
    "#             for i in range(left, right):\n",
    "#                 suml += stoneValue[i]\n",
    "#                 sumr = total - suml\n",
    "#                 if suml < sumr:\n",
    "#                     ans = max(ans, dfs(left, i) + suml)\n",
    "#                 elif suml > sumr:\n",
    "#                     ans = max(ans, dfs(i + 1, right) + sumr)\n",
    "#                 else:\n",
    "#                     ans = max(ans, max(dfs(left, i), dfs(i + 1, right)) + suml)\n",
    "#             return ans\n",
    "        \n",
    "#         n = len(stoneValue)\n",
    "#         return dfs(0, n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        pres = list(accumulate(stoneValue, initial=0))\n",
    "        n = len(stoneValue)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            # print(l, r)\n",
    "            if l >= r:\n",
    "                return 0\n",
    "            res = -inf\n",
    "            for i in range(l, r):\n",
    "                left, right = pres[i + 1] - pres[l], pres[r + 1] - pres[i + 1]\n",
    "                if left == right:\n",
    "                    res = max(res, dfs(l, i) + left, dfs(i + 1, r) + right)\n",
    "                elif left < right:\n",
    "                    if res >= 2 * left:\n",
    "                        continue\n",
    "                    res = max(res, dfs(l, i) + left)\n",
    "                else:\n",
    "                    if 2 * right <= res:\n",
    "                        break\n",
    "                    res = max(res, dfs(i + 1, r) + right)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        # 前缀和\n",
    "        S = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            S[i] = S[i-1] + stoneValue[i-1]\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            total = S[j+1] - S[i]\n",
    "            sum = 0\n",
    "            count = 0\n",
    "            for k in range(i,j+1):\n",
    "                sum += stoneValue[k]\n",
    "                if sum == total-sum:\n",
    "                    count = max(sum + max(dfs(i,k),dfs(k+1,j)),count)\n",
    "                elif sum < total-sum:\n",
    "                    # 剪个枝\n",
    "                    if count >= 2*sum:\n",
    "                        continue\n",
    "                    count = max(sum+dfs(i,k),count)\n",
    "                else:\n",
    "                    # 剪个枝\n",
    "                    if 2*(total - sum) <= count:\n",
    "                        break\n",
    "                    count = max(count,total-sum+dfs(k+1,j))\n",
    "            return count    \n",
    "        return dfs(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        # 前缀和\n",
    "        S = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            S[i] = S[i-1] + stoneValue[i-1]\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            total = S[j+1] - S[i]\n",
    "            sum = 0\n",
    "            count = 0\n",
    "            for k in range(i,j+1):\n",
    "                sum += stoneValue[k]\n",
    "                if sum == total-sum:\n",
    "                    count = max(sum + max(dfs(i,k),dfs(k+1,j)),count)\n",
    "                elif sum < total-sum:\n",
    "                    # 剪个枝\n",
    "                    if count >= 2*sum:\n",
    "                        continue\n",
    "                    count = max(sum+dfs(i,k),count)\n",
    "                else:\n",
    "                    # 剪个枝\n",
    "                    if 2*(total - sum) <= count:\n",
    "                        break\n",
    "                    count = max(count,total-sum+dfs(k+1,j))\n",
    "            return count    \n",
    "        return dfs(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        sums = [0]\n",
    "        for i in stoneValue:\n",
    "            sums.append(i+sums[-1])\n",
    "\n",
    "        dp = [[(0, i) for __ in range(len(stoneValue)+1)] for i in range(len(stoneValue))]\n",
    "        for left in range(n-2, -1, -1):\n",
    "            for right in range(left+2, n+1):\n",
    "                p, q = sorted([dp[left+1][right][1], dp[left][right-1][1]])\n",
    "                for a in range(max(0, p-1), min(q+2, n)):\n",
    "                    l1, r1 = sums[a]-sums[left], sums[right]-sums[a]\n",
    "                    if l1 == r1:\n",
    "                        dp[left][right] = max(dp[left][right], (max(dp[left][a][0], dp[a][right][0])+l1, a))\n",
    "                    elif l1 > r1:\n",
    "                        dp[left][right] = max(dp[left][right], (dp[a][right][0]+r1, a))\n",
    "                    else:\n",
    "                        dp[left][right] = max(dp[left][right], (dp[left][a][0]+l1, a))\n",
    "        return dp[0][-1][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        sumv = [[0]*n for i in range(n)]\n",
    "        dp = [[0]*n for i in range(n)]\n",
    "        maxl = [[0]*n for i in range(n)]\n",
    "        maxr = [[0]*n for i in range(n)]\n",
    "        fenge = [[0]*n for i in range(n)]\n",
    "        for i in range(n):\n",
    "            sumv[i][i] = stoneValue[i]\n",
    "            maxl[i][i] = stoneValue[i]\n",
    "            maxr[i][i] = stoneValue[i]\n",
    "            fenge[i][i] = i+1\n",
    "        for l in range(1, n):\n",
    "            for i in range(n-l):\n",
    "                j = i+l\n",
    "                sumv[i][j] = sumv[i][j-1]+stoneValue[j]\n",
    "                dp[i][j] = -inf\n",
    "                fenge[i][j] = fenge[i][j-1]\n",
    "                while fenge[i][j] <= j and sumv[i][fenge[i][j]-1] <= sumv[fenge[i][j]][j]:\n",
    "                    fenge[i][j] += 1\n",
    "                fenge[i][j] -= 1\n",
    "                if fenge[i][j] > i and sumv[i][fenge[i][j]-1] <= sumv[fenge[i][j]][j]:\n",
    "                    dp[i][j] = max(dp[i][j], maxl[i][fenge[i][j]-1])\n",
    "                while fenge[i][j] > i and sumv[i][fenge[i][j]-1] >= sumv[fenge[i][j]][j]:\n",
    "                    fenge[i][j] -= 1\n",
    "                fenge[i][j] += 1\n",
    "                if fenge[i][j] <= j and sumv[i][fenge[i][j]-1] >= sumv[fenge[i][j]][j]:\n",
    "                    dp[i][j] = max(dp[i][j], maxr[fenge[i][j]][j])\n",
    "                maxl[i][j] = max(maxl[i][j-1], sumv[i][j] + dp[i][j])\n",
    "                maxr[i][j] = max(maxr[i+1][j], sumv[i][j] + dp[i][j])\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        presum=list(accumulate(stoneValue,initial=0))\n",
    "        @cache\n",
    "        def dfs(left,right):\n",
    "            ans=0            \n",
    "            for mid in range(left,right):\n",
    "                t1=presum[mid]-presum[left]\n",
    "                t2=presum[right]-presum[mid]\n",
    "                if t1<t2:\n",
    "                    if ans>=2*t1:continue\n",
    "                    ans=max(ans,dfs(left,mid)+t1)\n",
    "                elif t1>t2:\n",
    "                    if ans>=2*t2:continue\n",
    "                    ans=max(ans,dfs(mid,right)+t2)\n",
    "                else:##t1==t2\n",
    "                    ans=max(ans,dfs(left,mid)+t1,dfs(mid,right)+t2)\n",
    "                    break\n",
    "            return ans\n",
    "        return dfs(0,len(stoneValue))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        sums = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            sums[i + 1] = sums[i] + stoneValue[i]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get(l, r):\n",
    "            if l == r:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for j in range(l, r):\n",
    "                t0 = sums[j + 1] - sums[l]\n",
    "                t1 = sums[r + 1] - sums[j + 1]\n",
    "                t = min(t0, t1)\n",
    "                if t * 2 <= res:\n",
    "                    break\n",
    "                if t0 > t1:\n",
    "                    temp = get(j + 1, r) + t1\n",
    "                elif t0 < t1:\n",
    "                    temp = get(l, j) + t0\n",
    "                else:\n",
    "                    temp = t0 + max(get(j + 1, r), get(l, j))\n",
    "                res = max(res, temp)\n",
    "            return res\n",
    "\n",
    "        ans = get(0, n - 1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        s = list(itertools.accumulate(stoneValue, initial=0))\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            a, b = 0, s[j+1] - s[i]\n",
    "            # ans = min(f(i+1, j), f(i, j-1))\n",
    "            ans = 0\n",
    "            for k in range(i, j):\n",
    "                a += stoneValue[k]\n",
    "                b -= stoneValue[k]\n",
    "                if 2 * a < ans:\n",
    "                    continue\n",
    "                if 2 * b < ans:\n",
    "                    break\n",
    "                if a <= b and (x := f(i, k) + a) > ans:\n",
    "                    ans = x\n",
    "                if a >= b and (x := f(k+1, j) + b) > ans:\n",
    "                    ans = x\n",
    "            return ans\n",
    "        \n",
    "        return f(0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        sums = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            sums[i + 1] = sums[i] + stoneValue[i]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get(l, r):\n",
    "            if l == r:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for j in range(l, r):\n",
    "                t0 = sums[j + 1] - sums[l]\n",
    "                t1 = sums[r + 1] - sums[j + 1]\n",
    "                t = min(t0, t1)\n",
    "                if t * 2 < res:\n",
    "                    break\n",
    "                if t0 > t1:\n",
    "                    temp = get(j + 1, r) + t1\n",
    "                elif t0 < t1:\n",
    "                    temp = get(l, j) + t0\n",
    "                else:\n",
    "                    temp = t0 + max(get(j + 1, r), get(l, j))\n",
    "                res = max(res, temp)\n",
    "            return res\n",
    "\n",
    "        ans = get(0, n - 1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n=len(stoneValue)\n",
    "        pre=[0]*(n+1)\n",
    "        for i,e in enumerate(stoneValue):\n",
    "            pre[i+1]=pre[i]+e\n",
    "        print(pre)\n",
    "        @cache    \n",
    "        def dfs(l,r):\n",
    "            if l==r:\n",
    "                return 0\n",
    "            if r-l==1:\n",
    "                return min(stoneValue[l],stoneValue[r])\n",
    "            total=pre[r+1]-pre[l]\n",
    "            res=ls=0\n",
    "            for last in range(l,r):\n",
    "                ls+=stoneValue[last]\n",
    "                rs=total-ls     \n",
    "                if ls>rs:\n",
    "                    dr=dfs(last+1,r)\n",
    "                    if dr+rs>res:\n",
    "                        res=dr+rs\n",
    "                elif ls<rs:\n",
    "                    dr=dfs(l,last)\n",
    "                    if dr+ls>res:\n",
    "                        res=dr+ls\n",
    "                else:\n",
    "                    dr=max(dfs(last+1,r)+rs,dfs(l,last)+ls)\n",
    "                    if dr>res:\n",
    "                        res=dr\n",
    "            #print(l,r,res)\n",
    "            return res\n",
    "        return dfs(0,n-1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        n = len(stoneValue)\n",
    "        s = list(itertools.accumulate(stoneValue, initial=0))\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            if i == j:\n",
    "                return 0\n",
    "            a, b = 0, s[j+1] - s[i]\n",
    "            ans = 0\n",
    "            for k in range(i, j):\n",
    "                a += stoneValue[k]\n",
    "                b -= stoneValue[k]\n",
    "                if a <= b and (x := f(i, k) + a) > ans:\n",
    "                    ans = x\n",
    "                if a >= b and (x := f(k+1, j) + b) > ans:\n",
    "                    ans = x\n",
    "            return ans\n",
    "        \n",
    "        return f(0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: list[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j):\n",
    "            if i>=j:\n",
    "                return 0\n",
    "            ans=0\n",
    "            half=(presum[j+1]+presum[i])/2\n",
    "            idx=bisect.bisect_left(presum,half,lo=i,hi=j+1)\n",
    "            if presum[idx]==half:\n",
    "                ans=max(ans,left_dfs(i,idx),right_dfs(idx,j))\n",
    "            else:\n",
    "                ans=max(ans,left_dfs(i,idx-1))\n",
    "                ans=max(ans,right_dfs(idx,j))\n",
    "            return ans\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def left_dfs(i,j):\n",
    "            if i>=j:\n",
    "                return 0\n",
    "            return max(presum[j]-presum[i]+dfs(i,j-1),left_dfs(i,j-1))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def right_dfs(i,j):\n",
    "            if i>=j+1:\n",
    "                return 0\n",
    "            return max(presum[j+1]-presum[i]+dfs(i,j),right_dfs(i+1,j))\n",
    "\n",
    "        presum=[0]+list(accumulate(stoneValue))\n",
    "        return dfs(0,len(stoneValue)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            half = (presum[j + 1] + presum[i]) / 2\n",
    "            # 使用二分查找左右的大小中心位置\n",
    "            idx = bisect.bisect_left(presum, half, lo=i, hi=j + 1)\n",
    "            # idx 左边, left更小; idx 右边, right更小\n",
    "            if presum[idx] == half:\n",
    "                ans = max(ans, left_dfs(i, idx), right_dfs(idx, j))\n",
    "            else:\n",
    "                ans = max(ans, left_dfs(i, idx-1))\n",
    "                ans = max(ans, right_dfs(idx, j))\n",
    "            return ans\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def left_dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            return max(presum[j] - presum[i] + dfs(i, j-1), left_dfs(i, j-1))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def right_dfs(i, j):\n",
    "            if i >= j+1:\n",
    "                return 0\n",
    "            return max(presum[j+1] - presum[i] + dfs(i, j), right_dfs(i+1, j))\n",
    "\n",
    "        presum = [0] + list(accumulate(stoneValue))\n",
    "        return dfs(0, len(stoneValue) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            half = (presum[j + 1] + presum[i]) / 2\n",
    "            # 使用二分查找左右的大小中心位置\n",
    "            idx = bisect.bisect_left(presum, half, lo=i, hi=j + 1)\n",
    "            # idx 左边, left更小; idx 右边, right更小\n",
    "            if presum[idx] == half:\n",
    "                ans = max(ans, left_dfs(i, idx), right_dfs(idx, j))\n",
    "            else:\n",
    "                ans = max(ans, left_dfs(i, idx-1))\n",
    "                ans = max(ans, right_dfs(idx, j))\n",
    "            return ans\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def left_dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            return max(presum[j] - presum[i] + dfs(i, j-1), left_dfs(i, j-1))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def right_dfs(i, j):\n",
    "            if i >= j+1:\n",
    "                return 0\n",
    "            return max(presum[j+1] - presum[i] + dfs(i, j), right_dfs(i+1, j))\n",
    "\n",
    "        presum = [0] + list(accumulate(stoneValue))\n",
    "        return dfs(0, len(stoneValue) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            half = (presum[j + 1] + presum[i]) / 2\n",
    "            # 使用二分查找左右的大小中心位置\n",
    "            idx = bisect.bisect_left(presum, half, lo=i, hi=j + 1)\n",
    "            # idx 左边, left更小; idx 右边, right更小\n",
    "            if presum[idx] == half:\n",
    "                ans = max(ans, left_dfs(i, idx), right_dfs(idx, j))\n",
    "            else:\n",
    "                ans = max(ans, left_dfs(i, idx-1))\n",
    "                ans = max(ans, right_dfs(idx, j))\n",
    "            return ans\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def left_dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            return max(presum[j] - presum[i] + dfs(i, j-1), left_dfs(i, j-1))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def right_dfs(i, j):\n",
    "            if i >= j+1:\n",
    "                return 0\n",
    "            return max(presum[j+1] - presum[i] + dfs(i, j), right_dfs(i+1, j))\n",
    "\n",
    "        presum = [0] + list(accumulate(stoneValue))\n",
    "        return dfs(0, len(stoneValue) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            half = (presum[j + 1] + presum[i]) / 2\n",
    "            # 使用二分查找左右的大小中心位置\n",
    "            idx = bisect.bisect_left(presum, half, lo=i, hi=j + 1)\n",
    "            # idx 左边, left更小; idx 右边, right更小\n",
    "            if presum[idx] == half:\n",
    "                ans = max(ans, left_dfs(i, idx), right_dfs(idx, j))\n",
    "            else:\n",
    "                ans = max(ans, left_dfs(i, idx-1))\n",
    "                ans = max(ans, right_dfs(idx, j))\n",
    "            return ans\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def left_dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            return max(presum[j] - presum[i] + dfs(i, j-1), left_dfs(i, j-1))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def right_dfs(i, j):\n",
    "            if i >= j+1:\n",
    "                return 0\n",
    "            return max(presum[j+1] - presum[i] + dfs(i, j), right_dfs(i+1, j))\n",
    "\n",
    "        presum = [0] + list(accumulate(stoneValue))\n",
    "        return dfs(0, len(stoneValue) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            half = (presum[j + 1] + presum[i]) / 2\n",
    "            # 使用二分查找左右的大小中心位置\n",
    "            idx = bisect.bisect_left(presum, half, lo=i, hi=j + 1)\n",
    "            # idx 左边, left更小; idx 右边, right更小\n",
    "            if presum[idx] == half:\n",
    "                ans = max(ans, left_dfs(i, idx), right_dfs(idx, j))\n",
    "            else:\n",
    "                ans = max(ans, left_dfs(i, idx-1))\n",
    "                ans = max(ans, right_dfs(idx, j))\n",
    "            return ans\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def left_dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            return max(presum[j] - presum[i] + dfs(i, j-1), left_dfs(i, j-1))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def right_dfs(i, j):\n",
    "            if i >= j+1:\n",
    "                return 0\n",
    "            return max(presum[j+1] - presum[i] + dfs(i, j), right_dfs(i+1, j))\n",
    "\n",
    "        presum = [0] + list(accumulate(stoneValue))\n",
    "        return dfs(0, len(stoneValue) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            half = (presum[j + 1] + presum[i]) / 2\n",
    "            # 使用二分查找左右的大小中心位置\n",
    "            idx = bisect.bisect_left(presum, half, lo=i, hi=j + 1)\n",
    "            # idx 左边, left更小; idx 右边, right更小\n",
    "            if presum[idx] == half:\n",
    "                ans = max(ans, left_dfs(i, idx), right_dfs(idx, j))\n",
    "            else:\n",
    "                ans = max(ans, left_dfs(i, idx-1))\n",
    "                ans = max(ans, right_dfs(idx, j))\n",
    "            return ans\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def left_dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            return max(presum[j] - presum[i] + dfs(i, j-1), left_dfs(i, j-1))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def right_dfs(i, j):\n",
    "            if i >= j+1:\n",
    "                return 0\n",
    "            return max(presum[j+1] - presum[i] + dfs(i, j), right_dfs(i+1, j))\n",
    "\n",
    "        presum = [0] + list(accumulate(stoneValue))\n",
    "        return dfs(0, len(stoneValue) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameV(self, stoneValue: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            half = (presum[j + 1] + presum[i]) / 2\n",
    "            # 使用二分查找左右的大小中心位置\n",
    "            idx = bisect.bisect_left(presum, half, lo=i, hi=j + 1)\n",
    "            # idx 左边, left更小; idx 右边, right更小\n",
    "            if presum[idx] == half:\n",
    "                ans = max(ans, left_dfs(i, idx), right_dfs(idx, j))\n",
    "            else:\n",
    "                ans = max(ans, left_dfs(i, idx-1))\n",
    "                ans = max(ans, right_dfs(idx, j))\n",
    "            return ans\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def left_dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            return max(presum[j] - presum[i] + dfs(i, j-1), left_dfs(i, j-1))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def right_dfs(i, j):\n",
    "            if i >= j+1:\n",
    "                return 0\n",
    "            return max(presum[j+1] - presum[i] + dfs(i, j), right_dfs(i+1, j))\n",
    "\n",
    "        presum = [0] + list(accumulate(stoneValue))\n",
    "        return dfs(0, len(stoneValue) - 1)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
